#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;

template<class T> 
void QuickSort(vector<T>& v, int begin,int end)
{
	if (begin >= end) {
		return;
	}
	int pos = begin;
	int left = begin;
	int right = end;
	while (left < right) {
		while (left<right && v[right]>v[pos]) {
			right--;
		}
		while (left < right && v[left] < v[pos]) {
			left++;
		}
		swap(v[left], v[right]);
	}
	swap(v[pos], v[left]);
	QuickSort(v, begin, left - 1);
	QuickSort(v, left + 1, end);

}
template<class T>
void Print(const vector<T>& v, int size) {
	for (int i = 0; i < size; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}
void test() {
	vector<int>v{ 5,6,8,-3,2,1,9,-1,7,4,-2 };
	Print(v, v.size());
	QuickSort(v,0,v.size()-1);
	Print(v, v.size());
}
int main() {
	test();
	return 0;
}